package leetcode;

import Tree.TreeNode;

//完全二叉树的结点个数
public class CompleteTreeNodes {

	public int countNodes(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int leftDepth = getDepth(root.left);
		int rightDepth = getDepth(root.right);
		if (leftDepth == rightDepth) {
			// 此时左子树是完全二叉树
			return (1 << leftDepth) + countNodes(root.right);
		} else {
			// 此时左子树的深度比右子树多1，但右子树是完全二叉树
			return (1 << rightDepth) + countNodes(root.left);
		}
	}

	public int getDepth(TreeNode node) {
		if (node == null) {
			return 0;
		}
		return 1 + getDepth(node.left);
	}
	
	//another more efficient code
	
//	Basically my solution contains 2 steps.
//	(1) Firstly, we need to find the height of the binary tree and count the nodes above the last level.
//	(2) Then we should find a way to count the nodes on the last level.
	
//	Here I used a kind of binary search. We define the "midNode" of the last level as a node following 
//	the path "root->left->right->right->...->last level".
	
//	If midNode is null, then it means we should count the nodes on the last level in the left subtree.

//	If midNode is not null, then we add half of the last level nodes to our result and then count the nodes 
//	on the last level in the right subtree.


	public int countNodes2(TreeNode root) {
		if (root == null)
			return 0;
		if (root.left == null)
			return 1;
		//height从0算起
		int height = 0;
		int nodesSum = 0;
		TreeNode curr = root;
		while (curr.left != null) {
			nodesSum += (1 << height);
			height++;
			curr = curr.left;
		}
		return nodesSum + countLastLevel(root, height);
	}

//	Of course I used some stop condition to make the code more efficient, e.g. 
//	when a tree has height 1, it means it only has 3 cases: 1. has right son; 2. only has left son; 3. has no son.
	
//	计算最后一层的结点数
	private int countLastLevel(TreeNode root, int height) {
		//这个height是从0算起的，所以有点不一样
		if (height == 1){
			if (root.right != null)
				return 2;
			else if (root.left != null)
				return 1;
			else
				return 0;
		}
		TreeNode midNode = root.left;
		int currHeight = 1;
		while (currHeight < height) {
			currHeight++;
			midNode = midNode.right;
		}
		if (midNode == null)
			return countLastLevel(root.left, height - 1);
		else
			//1 <<(height - 1)是最底层中左子树的结点数
			return (1 << (height - 1)) + countLastLevel(root.right, height - 1);
	}
}
